This invention relates to a decoding apparatus and method and a program, and more particularly to a decoding apparatus and method and a program by which the decoding performance can be enhanced in a technique of error correction codes which uses an algebraic procedure.
As a decoding method for algebraic-geometric codes such as, for example, the Reed-Solomon codes or BCH (Bose-Chaudhuri-Hocquenghem) codes which are subfield partial codes of the Reed-Solomon codes, a method is known which makes use of an algebraic property and is superior in both of the performance cost and the calculation cost.
For example, if Reed Solomon codes of a code length n, an information length k, a definition body GF(q) (q=pm, p: prime number) and a minimum distance d=n−k are represented by RS(n, k), then a critical distance decoding method of decoding a hard decision reception word into a codeword having a minimum Hamming distance is well known as a method which assures correction of t error symbols where t satisfies t<d/2. Further, list decoding by Guruswami-Sudan (hereinafter referred to as G-S list decoding) method assures correction of t error symbols where T<√{square root over ( )}nk is satisfied, as disclosed in V. Guruswami, M. Sudan, “Improved decoding of Reed-Solomon and Algebraic-Geometry codes”, IEEE Transactions on Information Theory, Vol. 45, pp. 1757 to 1767, 1999.
It is known that list decoding by Koetter-Vardy which uses a soft decision reception word (such list decoding is hereinafter referred to as K-V list decoding) as an extended version of the G-S list decoding described above includes four procedures including calculation of the reliability values of symbols from reception information, extraction of two-variable polynomial interpolation conditions from the reliability values, interpolation of two-variable polynomials and production of a decoded word list by factorization of the interpolation polynomials. Thus, the K-V list decoding has a higher performance than the hard decision decoding. The K-V list decoding is disclosed, for example, in R. Koetter, A. Vardy, “Algebraic soft-decision decoding of Reed-Solomon codes”, IEEE Transactions on Information Theory, 2001. Also a method of reducing the calculation cost to a realistic level by re-encoding is known and disclosed, for example, in R. Koetter, J. Ma, A. Vardy, A. Ahmed, “Efficient Interpolation and Factorization in Algebraic Soft-Decision Decoding of Reed-Solomon codes”, Proceedings of ISIT 2003.
Meanwhile, attention is paid recently to Low Density Parity-check Codes (LDPC) as linear codes by which a high performance proximate to a marginal performance can be obtained through repetitive decoding using belief propagation. The Low Density Parity-check Codes are disclosed in D. MacKay, “Good Error-Correcting Codes Based on Very Sparse Matrices”, IEEE Transactions on Information Theory, 1999.
It is theoretically known that the belief propagation used in the LDPC codes is generally effective only for linear codes having a low density parity check matrix. Meanwhile, to reduce the density of a parity check matrix of the Reed-Solomon codes or the BCH codes is known as an NP-hard problem as disclosed in Berlekamp, R. McEliece, H. van Tilborg, “On the inherent intractability of certain coding problems”, IEEE Transactions on Information Theory, vol. 24, pp. 384 to 386, May 1978.
From the foregoing, it has been believed difficult to apply a decoding method in which the belief propagation is used to the Reed-Solomon codes or the BCH codes.
However, it was proved in 2004 by Narayanan et al. that use of a parity-check matrix for which diagonalization is performed in accordance with the reliability of a reception word allows effective application of a decoding method in which the belief propagation is used to the Reed-Solomon codes, BCH codes and other linear codes having a parity-check matrix whose density is not low, as disclosed in Jing Jiang, K. R. Narayanan, “Soft Decision Decoding of RS Codes Using Adaptive Parity Check Matrices”, Proceedings of IEEE International Symposium on Information Theory 2004. In the following, the ABP (Adaptive Belief Propagation) decoding method is described.
For example, linear codes C which have a code length n of 6, an information length k of 3 and an encoding ratio r of ½ and has such a 3×6 matrix H as given as an expression (1) below as a parity-check matrix is considered:
                    H        =                  (                                                    1                                            0                                            1                                            0                                            0                                            1                                                                    1                                            1                                            0                                            1                                            0                                            1                                                                    0                                            1                                            1                                            1                                            1                                            1                                              )                                    (        1        )            
where the code space C is given by the following expression (2):C={c=(c1,c2, . . . , c6),c1,c2, . . . , c6ε0,1|H·ct=0}  (2)
It is assumed that a certain codeword passes through a channel, for example, a certain codeword passes through an AWGN (Adaptive While Gaussian Noise) channel after BPSK (Binary Phase Shift Keying) modulation, and then is received as a reception word as given by the following expression (3) by a receiver:y=(y1,y2, . . . , y6)=(0.4,1.2,0.1,0.7,0.3,0.7)  (3)
A flow of a decoding process executed by a decoding apparatus of the receiver in such an instance as just described is described below with reference to a flow chart of FIG. 1.
First at step S1, the decoding apparatus searches for a reliability order of a reception word. The decoding apparatus performs ranking of reception symbols (terms on the right side of the expression (3) above) of the received reception word determining the magnitude of the absolute value of each reception symbol as the height of the reliability of the reception symbol. In particular, the decoding apparatus applies numbers to the reception symbols in an ascending order of the reliability, for example, as represented by numerals surrounded by circles in the following expression (4):
                    y        =                  (                                    0.4                                      ,                          1.2                                      ,                          0.1                                      ,                          0.7                                      ,                          0.3                                      ,                          0.7                                              )                                    (        4        )            
Then, at step S2, the decoding apparatus re-arranges the thus ranked reception symbols in accordance with a predetermined rule to convert the order of priority ranks of the symbols. This rule is prepared in advance and includes a plurality of sub rules different form each other and equal to the number of times of outer repetition as hereinafter described, and every time outer repetition is performed, a different one of the sub rules is selected.
After the decoding apparatus converts the order, it performs diagonalization of a parity check matrix H in accordance with the order at step S3. For example, where the priority ranks are applied to the reception symbols in an ascending order of the reliability by the conversion of the order, the decoding performs the diagonalization of the parity check matrix H in order beginning with a column corresponding to a symbol whose reliability is lowest.
For example, where the reliability ranks of the reception symbols are such as indicated by the expression (4) given hereinabove, the column of the parity check matrix H which corresponds to a symbol whose reliability is the lowest is the third column, and the column of the parity check matrix H which corresponds to a symbol whose reliability is the second lowest is the fifth column. Further, the column of the parity check matrix H which corresponds to a symbol whose reliability of the third lowest is the first column, and the column of the parity check matrix H which corresponds to a symbol whose reliability is the fourth lowest is the fourth or sixth column while the column of the parity check matrix H which corresponds to a symbol whose reliability is the highest is the second column. The decoding apparatus performs diagonalization of the parity check matrix H in accordance with the priority ranks.
In particular, the decoding apparatus first performs basic transformation of the parity check matrix H focusing on the third column. More particularly, the decoding apparatus first exclusively ORs the first row and the third row so that the third column may be “100” to obtain a new third row thereby to convert the parity check matrix H into the following expression (5):
                    H        =                  (                                                    1                                            0                                            1                                            0                                            0                                            1                                                                    1                                            1                                            0                                            1                                            0                                            1                                                                    1                                            1                                            0                                            1                                            1                                            0                                              )                                    (        5        )            
Then, the decoding apparatus performs basic transformation of the parity check matrix H focusing on the fifth column. In particular, the decoding apparatus exchanges the second row and the third row so that the fifth column may be “010” to convert the parity check matrix H into the following expression (6):
                    H        =                  (                                                    1                                            0                                            1                                            0                                            0                                            1                                                                    1                                            1                                            0                                            1                                            1                                            0                                                                    1                                            1                                            0                                            1                                            0                                            1                                              )                                    (        6        )            
Thereafter, the decoding apparatus performs basic transformation of the parity check matrix H focusing on the first column. In particular, the decoding apparatus substitutes exclusive OR values of the first row and the third row into the first row and substitutes exclusive OR values of the second row and the third row into the that the first column may be “001” to convert the parity check matrix H into such a parity check matrix Hnew as indicated by the following expression (7)
                    H        =                  (                                                    0                                            1                                            1                                            1                                            0                                            0                                                                    0                                            0                                            0                                            0                                            1                                            1                                                                    1                                            1                                            0                                            1                                            0                                            1                                              )                                    (        7        )            
It is to be noted that, if a column for which it is attempted to perform diagonalization is linearly dependent to a column which has been diagonalized precedently, then the decoding apparatus leaves the column as it is and attempts diagonalization with regard to a column of the next rank. The decoding apparatus performs diagonalization by a number of times equal to the number of ranks of the parity check matrix H in this manner to obtain a new parity check matrix Hnew. Then, the decoding apparatus uses the resulting parity check matrix Hnew to update the reliability values by the belief propagation at step S4.
FIG. 2 is a Tanner graph corresponding to the parity check matrix Hnew indicated by the expression (7) above. The belief propagation is implemented by propagating a message along an edge of the Tanner graph. Referring to FIG. 2, variable nodes 11 to 16 correspond to the columns of the matrix (in the case of FIG. 2, the parity check matrix Hnew) . Check nodes 21 to 23 correspond to the rows of the matrix (in the case of FIG. 2, the parity check matrix Hnew).
In the following description, i and j are natural numbers, and a message from the ith variable node to the jth check node is represented by Ri,j; a message from the jth check node to the ith variable node is represented by Qi,j; an index set of check nodes connecting to the ith variable node is represented by J(i); and an index set of variable nodes connecting to the jth check node is represented by I(j).
In this instance, updating expressions of the message Ri,j and the message Qi,j are represented as given by the following expressions (8) and (9), respectively:Ri,j=2 tan h−1(π|εI(j)\i tan h(Qi,j/2))  (8)Qi,j=ri+θΣiεJ(i)\jRi,I  (9)
where the coefficient θ is a convergence factor called vertical step damping factor and has a value defined by 0<θ≦1. A reception symbol yj is set as an initial value of the message Qi,j, and updating of extrinsic informationΛjx is performed in accordance with the following expression (10):
                              Λ          i          x                =                              ∑                          l              ∈                              J                ⁡                                  (                  i                  )                                                              ⁢                      R                          i              ,              l                                                          (        10        )            
Thus, the decoding apparatus calculates, at step S5 of FIG. 1, a Log Likelihood Ratio (LLR) Λq of each code symbol in accordance with the following expression (11):Λiq=ri+α1Λix  (11)
where the coefficient α1 is a convergence factor called adaptive belief propagation damping factor and has a value defined by 0<α≦1.
After the decoding apparatus calculates the LLR values, it advances the processing to step S6, at which it searches for the reliability order of the calculated LLR values. In particular, the decoding apparatus determines the magnitudes of the absolute values of the calculated LLR values as reliability values and searches for the order of the reliability values. As hereinafter described, updating of the LLR values is performed repetitively until after a predetermined condition is satisfied. The search for the reliability order is performed for next time updating (diagonalization of the parity check matrix H).
Then at step S7, the decoding apparatus decodes the LLR values calculated (updated) in such a manner as described above to obtain decoded words. The decoding method may be, for example, hard decision decoding, critical distance decoding, or K-V list decoding. Then at step S8, the decoding apparatus decides whether or not an inner repetitive decoding stopping condition SC1 which is a condition determined in advance is satisfied.
Updating of the LLR values by the belief propagation is repeated until after repetitive decoding stopping condition SC prepared in advance is satisfied. The decoding apparatus uses the reliability values of the LLR values updated by the belief propagation to update the LLR values again. In particular, the decoding apparatus can update the LLR values by new belief propagation by determining the magnitudes of the absolute values of the resulting LLR values as reliability values and performing diagonalization of the columns of the parity check matrix in an ascending order of the reliability values of the corresponding symbols. Then, every time the decoding apparatus updates the LLR values, it performs decoding using the resulting LLR values (performs decoding repetitively). This is hereinafter referred to as inner repetitive decoding. The decoding apparatus repeats the inner repetitive decoding until after the inner repetitive decoding stopping condition SC1 prepared in advance is satisfied.
In particular, if the decoding apparatus decides at step S8 of FIG. 1 that the inner repetitive decoding stopping condition SC1 is not satisfied, then it returns the processing to step S3 to repeat the processes at the steps beginning with step S3. On the other hand, if the decoding apparatus decides at step S8 that the inner repetitive decoding stopping condition SC1 is satisfied, then it advances the processing to step S9.
At step S9, the decoding apparatus decides whether or not an outer repetitive decoding stopping condition SC2 is satisfied. If the decoding apparatus decides that the outer repetitive decoding stopping condition SC2 is not satisfied, then it returns the processing to step S2 to repeat the processes at the steps beginning with step S2.
In particular, the decoding apparatus prepares a plurality of ranking methods different from each other in addition to the ranking method in which the reliability values of the reception values are used as initial values for the diagonalization priority ranks of the columns of the parity check matrix H. Then, the decoding apparatus performs the inner repetitive decoding described above by a plural number of times (repetitively performs the inner repetitive decoding) serially or parallelly using the plural ranking methods. This is hereinafter referred to as outer repetitive decoding. The decoding apparatus repeats the outer repetitive decoding until after the outer repetitive decoding stopping condition SC2 prepared in advance is satisfied.
An example of the repetitive decoding stopping condition SC where the object linear codes are the Reed-Solomon codes is described below.
For example, it is assumed that the maximum number times of repetition determined in advance is N and the hard-decision result of Λq is d=(d1, d2, . . . d6). Here, the hard-decision result di is represented as given by the following expression (12):di={1 if Λiq>0,0 if Λiq≦0}  (12)
In this instance, the decoding apparatus can set it as the repetitive decoding stopping condition SC (inner repetitive decoding stopping condition SC1 or outer repetitive decoding stopping condition SC2), for example, that the value of the product of the parity check matrix H and the hard-decision result d is 0 (H·d=0) or the repetition number t is equal to or greater than the maximum number times of repetition determined in advance N (t≧N) (that is, at least one of the two conditions described is satisfied).
Alternatively, the decoding apparatus may set it as the repetitive decoding stopping condition SC (inner repetitive decoding stopping condition SC1 or outer repetitive decoding stopping condition SC2), for example, that critical distance decoding results in success or the repetition number t is equal to or greater than the maximum number times of repetition determined in advance N (t≧N) (that is, at least one of the two conditions described is satisfied). Otherwise, the decoding apparatus may set it as the repetitive decoding stopping condition SC (inner repetitive decoding stopping condition SC1 or outer repetitive decoding stopping condition SC2), for example, that K-V list decoding results in success or the repetition number t is equal to or greater than the maximum number times of repetition determined in advance N (t≧N) (that is, at least one of the two conditions described is satisfied). Or else, the decoding apparatus may set it as the repetitive decoding stopping condition SC (inner repetitive decoding stopping condition SC1 or outer repetitive decoding stopping condition SC2), for example, merely that the repetition number t is equal to or greater than the maximum number times of repetition determined in advance N (t≧N).
After such outer repetitive decoding as described above is performed, if the decoding apparatus decides at step S9 that the outer repetitive decoding stopping condition SC2 is satisfied, then it ends the decoding process.